package sol.leetcode;

import def.ListNode;
import utils.LinkedListUtils;

/**
 * Partition List
 */
public class Issue086 {
    public ListNode partition(ListNode head, int x) {
        ListNode lessHead = new ListNode(0), less = lessHead;
        ListNode greaterHead = new ListNode(0), greater = greaterHead;

        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                less.next = p;
                less = less.next;
                p = p.next;
                less.next = null;
            } else {
                greater.next = p;
                greater = greater.next;
                p = p.next;
                greater.next = null;
            }
        }
        less.next = greaterHead.next;
        return lessHead.next;
    }

    public static void main(String[] args) {
        ListNode root = LinkedListUtils.create(1, 4, 3, 2, 5, 2);
        Issue086 sol = new Issue086();
        root = sol.partition(root, 3);
        System.out.println(LinkedListUtils.print(root));
    }
}
